package com.likou.second_challenge;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;

public class q239 {

    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        int index = 0;
        Deque<Integer> deque = new ArrayDeque<>();

        int i = 0;
        for (; i < k; i++) {
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }
            deque.addLast(i);
        }

        ans[index] = nums[deque.peekFirst()];
        index++;
        for (; i < n; i++) {
            while (!deque.isEmpty() && i - deque.peekFirst() >= k) {
                deque.pollFirst();
            }

            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }
            deque.addLast(i);

            ans[index] = nums[deque.peekFirst()];
            index++;
        }

        return ans;
    }
}
